39. ①处应填（     ）

A. pre[i]=std::max(pre[i-1],a[i-1])

B. pre[i + 1]= std::max(pre[i],pre[i +1])

C. pre[i]= std::max(pre[i - 1],a[i])

D. pre[i]= std::max(pre[i],pre[i - 1])

答案：D，std::vectorpre(a + mid, a+r); 复制从a[mid]到a[r-1]的数组。然后计算这个数组的前缀最大值，即pre[i]是从0到i的数组的最大值。

40. ②处应填（     ）

A. a[j]< max

B. a[j]< a[i]

C. pre[j - mid]< max

D. pre[j - mid]> max

答案：B，找最大值在前半段还是后半段的分界点，比较容易混淆的是C选项，因为此时max还没有更新，所以不能让a[j]或pre[j-mid]跟max来比，只能跟a[i]来比。

41. ③处应填（     ）

A. (long long)(j - mid)* max

B. (long long)(j - mid)*(i - 1)* max

C. sum[j - mid]

D. sum[j - mid]*(i - 1)

答案：A，i为起点，终点在后半段， 且最大值在前半段的个数是(j-mid)个，此时最大值都是max。

42. ④处应填（     ）

A. (long long)(r - j)* max

B. (long long)(r - j)*(mid - i)* max

C. sum[r - mid]- sum[j - mid]

D. (sum[r - mid]- sum[j - mid])*(mid - i)

答案：C，i为起点，终点在后半段，且最大值在后半段的情况，最大值的和通过sum前缀和数组计算。

43. ⑤处应填（     ）

A. solve(0, n)

B. solve(0, n - 1)

C. solve(1,n)

D. solve(1, n - 1)

答案：A，因为line 12-14行，可以看到二分的结束条件是l+1==r，而且此时取l的值，也就是说[l,r)，左闭右开的区间。

完善程序题2 整体解析：

分治算法，分为三部分来计算，1) 起点终点都在前半段；2) 都在后半段；3) 起点在前半段、终点在后半段。前两部分递归解决，难点在于第三部分。预处理后半段的两个数组，pre数组表示前缀数组的最大值（pre数组一定是单调不下降的），sum数组是pre数组前缀和。然后用双指针，前半段从后往前，维护最大值，后半段从前往后。